package xyz.scootaloo.oj.offer

import org.junit.Test
import xyz.scootaloo.console.app.support.Tester

/**
 * @author flutterdash@qq.com
 * @since 2021/4/13 11:26
 */
class P10II {

    /**
     * 1 1
     * 2 1
     * 3 2
     * 4 3
     * 5 5
     * 6 8
     * 7 13
     * 8 21
     */
    private fun numWays(n: Int): Int {
        return fib(n)
    }

    private fun fib(n: Int): Int {
        if (n < 0) return 0
        if (n <= 1) return 1

        val dp = intArrayOf(1, 2)
        for (count in 2 until n) {
            val sum = (dp[0] + dp[1]) % 1000000007
            dp[0] = dp[1]
            dp[1] = sum
        }
        return dp[1]
    }

    @Test
    fun test0() {
        Tester.createTest(this::numWays)
            .addCase(2, 2)
            .addCase(7, 21)
            .addCase(0, 1)
            .addCase(44, 134903163)
            .testAndShow()
    }

}
